丹崽的技术博客

一.子查询

我们平时在查询数据的时候，特别是报表数据的时候，或多或少都会接触到 子查询 这个东西的吧。因为有些数据，他就是需要前套一层 子查询 来先拿到部分数据，然后再结合这部分的数据接着进行查询。

二.子查询出现的位置

子查询出现的位置，如果平时没有去总结一下的话，还真的不知道可以在这么多的地方出现。具体来说呢，好像每个地方都可以出现。

2.1 SELECT位置

比如 SELECT (SELECT * FROM business_order);，当然这个语句好像并没有什么意义。

2.2 FROM位置

有个场景，比如订单表在已经支付的时候我们需要批量的去修改其他列的数据，那么我们会写：

1
2

UPDATE business_order SET status = 'DEL'
WHERE id IN (SELECT id FROM business_order WHERE xxx);

这条语句乍一看没有问题，但是 MySQL 会给你报个错误：You can't specify target table 'student' for update in FROM clause，意思大概就是无法对查询的表进行更新。 那么我们这个需求又必须要实现咋办呢，在条件中套多一层：

1
2
3
4

UPDATE business_order SET status = 'DEL'
WHERE id IN (
  SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a
);

那么上面的 SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a 语句有另外一个子查询出现在 FROM 位置

2.3 WHERE位置

详见 FROM位置 里面的示例，WHERE id IN ( SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a); 就是一个出现在 WHERE 位置的 子查询。

2.4 其他没有意义的地方

ORDER BY GROUP BY 都是可以出现子查询的，但是并没有什么意义，就不说了。

三.子查询的分类

单独看分类这一节并没有什么意义，但因为在下面讨论查询方式的时候，需要用到这些名字。所以大概记住一个名字代表什么意思然后带着这个名字去看下面就好了。

划分维度有几个，不过我直接挑出来常用的就好了。 其实就是一个问题：跟外查询有没有关系？

3.1 有关系：相关子查询

为了有个例子，我憋着气也要写一个可以执行的带有子查询的语句：

1
2
3
4
5
6
7

SELECT * FROM 
student stu 
WHERE id IN (
  SELECT stu_id 
  FROM scope scp 
  WHERE scp.stu_id = stu.id
);

（我怎么会写这么无聊的代码…….. 可以看到吧，子查询 中的 scope 条件中出现了依赖外部表 student 的条件，这种查询方法就是 相关子查询。

3.2 没有关系：非相关子查询

这个简单，就是子查询直接拿到外部，还可以继续执行的语句，因为并不需要依赖外部表的值。

四.子查询执行过程

上面是关联的方式，那接下来需要根据不同的查询方式进行分类。

4.1 标量子查询

举个例子：

1
2
3
4
5

SELECT * FROM 
student stu 
WHERE id = (
    SELECT stu_id FROM scope
)

就是外部表的一个列等于（或者其他 bool表达式 如 > < ）另外一个子查询的时候，就是 标量子查询。

4.2 行子查询

1
2
3
4
5

SELECT * FROM 
student stu 
WHERE (id, name) = (
    SELECT stu_id, stu_name FROM scope
)

4.3 标量子查询和行子查询的两种不同子查询

4.3.1 不相关子查询

那标量子查询、行子查询是怎么进行不相关子查询的，其实不是很难： 就当成两个简单的查询就好了，先执行 SELECT stu_id FROM scope 然后再执行 SELECT * FROM student stu WHERE id = 上面结果集

4.3.2 相关子查询

相关子查询就比较麻烦了，需要两个表每个记录去循环，看是否同时满足外部查询和内部查询的条件，如果满足才加入结果集。 比如这个：

1
2
3
4
5
6
7

SELECT * FROM 
student stu 
WHERE id IN (
  SELECT stu_id 
  FROM scope scp 
  WHERE scp.stu_id = stu.id AND scp.scope > 90
);

会先从 student 拿出 id=1 的记录，加入成绩表的查询，看看成绩是否大于90分，如果大于90分加入结果集返回，然后再拿出 id=2 的记录。

4.4 IN子查询

4.4.1 临时表查询

IN 查询和上面两种方式不一样，因为为了防止一些问题，比如 IN ...some sql 中，后面 SQL 语句查询出来的结果集很大，可能会导致内存不足，也会因为结果集过于庞大，外部表在查询的时候无法有效的使用到索引。 所以，IN子查询 会通过一些方式，将语句转换成 内连接 的形式来进行查询。 怎么转，通过 物化表 来做，例子说：

1
2
3
4
5
6
7

SELECT *
FROM student stu
WHERE id = (
    SELECT stu_id
  FROM student_parent stu_par
  WHERE stu_par.name LIKE '李%'
)

首先执行子查询，即查询学生的父母姓李的所有 stu_id 数据。 那么假设，这个系统刚运行没多久，那么这个结果集（只有一列因为我们指定了查询 stu_id，并且已经去重，比如某学生的父母都姓李，那么这张临时表只会保存一个 stu_id）将会被变为一张临时表（物化成一张表）存储在内存中，并且这个表是基于 HASH索引 而存在的，然后，将 student 表与内存中的这张表进行连接，比如内存中这张物化表的名字是 student_parent_memory 那么上面这条内连接的 SQL 将进一步变成：

1
2
3

SELECT stu.* 
FROM student stu 
INNER JOIN student_parent_memory spm ON stu.id = spm.*;

再假设，系统运行的不错，一直在运行着，那么子查询的表查询出来的结果集已经超过了数据库系统设置的 tmp_table_size 和 max_heap_table_size。那么这个临时表存储的位置将发生了变化，表来是内存的基于 HASH索引 的表，现在就变成了硬盘中基于 B+树 的表而存在。 至于后续如何进行，就是上一节中说的连接基于成本来判断使用哪张表做 驱动表 以及 被驱动表 的策略了。

4.4.2 半连接

半连接可以说，为了不像上面一样创建临时表或者优化创建的临时表，然后去进行查询的一种策略。 仅适用于不相关子查询 方式一 Table Pullout 把表拉出去 如果关联查询的子查询的结果集的那个列是唯一索引，那么子查询将被跳过生成临时表的步骤，然后被拉到外面直接内连查询！ 方式二 DuplicateWeedout execution strategy 消除重复值 生成一个只有一个列并且这个列 PRIMARY KEY，然后根据外部表的列来排除已经被加入到结果集的数据（因为这个列是唯一的）这种方式可以用于统计省市情况，由于满足某个条件（比如人口大于某个比率），而省可能包含很多个市，可能这个省多个市可以加入结果集，那么就可以使用这种方式来消除重复的省结果集。 方式三 LooseScan execution strategy 松散策略

1
2
3
4
5
6

SELECT * 
FROM order_info oi
WHERE order_id IN (
    SELECT order_id FROM deliver_bill db WHERE db.order_id LIKE 'XXX'
)
# deliver_bill 中 order_id 是二级索引

那么在执行子查询查发货单表的时候，由于 order_id 模糊查询，而且在发货单中可能存在很多重复的记录，那么在使用发货单二级索引的时候，就可以直接跳过这些重复的订单号值，拿到不重复的值就可以了。 方式四 Semi-join Materialization execution strategy 这是上面临时表策略 方式五 FirstMatch execution strategy 匹配字表跳出字表查询 从外表取出记录去一次一次匹配字表的记录，是一种最原始的方式。如果这条记录已经满足了条件，那么假如结果集，不再去匹配子表而是回到外表，继续下一条记录。

一.子查询

我们平时在查询数据的时候，特别是报表数据的时候，或多或少都会接触到 子查询 这个东西的吧。因为有些数据，他就是需要前套一层 子查询 来先拿到部分数据，然后再结合这部分的数据接着进行查询。

二.子查询出现的位置

子查询出现的位置，如果平时没有去总结一下的话，还真的不知道可以在这么多的地方出现。具体来说呢，好像每个地方都可以出现。

2.1 SELECT位置

比如 SELECT (SELECT * FROM business_order);，当然这个语句好像并没有什么意义。

2.2 FROM位置

有个场景，比如订单表在已经支付的时候我们需要批量的去修改其他列的数据，那么我们会写：

1
2

UPDATE business_order SET status = 'DEL'
WHERE id IN (SELECT id FROM business_order WHERE xxx);

这条语句乍一看没有问题，但是 MySQL 会给你报个错误：You can't specify target table 'student' for update in FROM clause，意思大概就是无法对查询的表进行更新。 那么我们这个需求又必须要实现咋办呢，在条件中套多一层：

1
2
3
4

UPDATE business_order SET status = 'DEL'
WHERE id IN (
  SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a
);

那么上面的 SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a 语句有另外一个子查询出现在 FROM 位置

2.3 WHERE位置

详见 FROM位置 里面的示例，WHERE id IN ( SELECT a.id FROM (SELECT id FROM business_order WHERE xxx) a); 就是一个出现在 WHERE 位置的 子查询。

2.4 其他没有意义的地方

ORDER BY GROUP BY 都是可以出现子查询的，但是并没有什么意义，就不说了。

三.子查询的分类

单独看分类这一节并没有什么意义，但因为在下面讨论查询方式的时候，需要用到这些名字。所以大概记住一个名字代表什么意思然后带着这个名字去看下面就好了。

划分维度有几个，不过我直接挑出来常用的就好了。 其实就是一个问题：跟外查询有没有关系？

3.1 有关系：相关子查询

为了有个例子，我憋着气也要写一个可以执行的带有子查询的语句：

1
2
3
4
5
6
7

SELECT * FROM 
student stu 
WHERE id IN (
  SELECT stu_id 
  FROM scope scp 
  WHERE scp.stu_id = stu.id
);

（我怎么会写这么无聊的代码…….. 可以看到吧，子查询 中的 scope 条件中出现了依赖外部表 student 的条件，这种查询方法就是 相关子查询。

3.2 没有关系：非相关子查询

这个简单，就是子查询直接拿到外部，还可以继续执行的语句，因为并不需要依赖外部表的值。

四.子查询执行过程

上面是关联的方式，那接下来需要根据不同的查询方式进行分类。

4.1 标量子查询

举个例子：

1
2
3
4
5

SELECT * FROM 
student stu 
WHERE id = (
    SELECT stu_id FROM scope
)

就是外部表的一个列等于（或者其他 bool表达式 如 > < ）另外一个子查询的时候，就是 标量子查询。

4.2 行子查询

1
2
3
4
5

SELECT * FROM 
student stu 
WHERE (id, name) = (
    SELECT stu_id, stu_name FROM scope
)

4.3 标量子查询和行子查询的两种不同子查询

4.3.1 不相关子查询

那标量子查询、行子查询是怎么进行不相关子查询的，其实不是很难： 就当成两个简单的查询就好了，先执行 SELECT stu_id FROM scope 然后再执行 SELECT * FROM student stu WHERE id = 上面结果集

4.3.2 相关子查询

相关子查询就比较麻烦了，需要两个表每个记录去循环，看是否同时满足外部查询和内部查询的条件，如果满足才加入结果集。 比如这个：

1
2
3
4
5
6
7

SELECT * FROM 
student stu 
WHERE id IN (
  SELECT stu_id 
  FROM scope scp 
  WHERE scp.stu_id = stu.id AND scp.scope > 90
);

会先从 student 拿出 id=1 的记录，加入成绩表的查询，看看成绩是否大于90分，如果大于90分加入结果集返回，然后再拿出 id=2 的记录。

4.4 IN子查询

4.4.1 临时表查询

IN 查询和上面两种方式不一样，因为为了防止一些问题，比如 IN ...some sql 中，后面 SQL 语句查询出来的结果集很大，可能会导致内存不足，也会因为结果集过于庞大，外部表在查询的时候无法有效的使用到索引。 所以，IN子查询 会通过一些方式，将语句转换成 内连接 的形式来进行查询。 怎么转，通过 物化表 来做，例子说：

1
2
3
4
5
6
7

SELECT *
FROM student stu
WHERE id = (
    SELECT stu_id
  FROM student_parent stu_par
  WHERE stu_par.name LIKE '李%'
)

首先执行子查询，即查询学生的父母姓李的所有 stu_id 数据。 那么假设，这个系统刚运行没多久，那么这个结果集（只有一列因为我们指定了查询 stu_id，并且已经去重，比如某学生的父母都姓李，那么这张临时表只会保存一个 stu_id）将会被变为一张临时表（物化成一张表）存储在内存中，并且这个表是基于 HASH索引 而存在的，然后，将 student 表与内存中的这张表进行连接，比如内存中这张物化表的名字是 student_parent_memory 那么上面这条内连接的 SQL 将进一步变成：

1
2
3

SELECT stu.* 
FROM student stu 
INNER JOIN student_parent_memory spm ON stu.id = spm.*;

再假设，系统运行的不错，一直在运行着，那么子查询的表查询出来的结果集已经超过了数据库系统设置的 tmp_table_size 和 max_heap_table_size。那么这个临时表存储的位置将发生了变化，表来是内存的基于 HASH索引 的表，现在就变成了硬盘中基于 B+树 的表而存在。 至于后续如何进行，就是上一节中说的连接基于成本来判断使用哪张表做 驱动表 以及 被驱动表 的策略了。

4.4.2 半连接

半连接可以说，为了不像上面一样创建临时表或者优化创建的临时表，然后去进行查询的一种策略。 仅适用于不相关子查询 方式一 Table Pullout 把表拉出去 如果关联查询的子查询的结果集的那个列是唯一索引，那么子查询将被跳过生成临时表的步骤，然后被拉到外面直接内连查询！ 方式二 DuplicateWeedout execution strategy 消除重复值 生成一个只有一个列并且这个列 PRIMARY KEY，然后根据外部表的列来排除已经被加入到结果集的数据（因为这个列是唯一的）这种方式可以用于统计省市情况，由于满足某个条件（比如人口大于某个比率），而省可能包含很多个市，可能这个省多个市可以加入结果集，那么就可以使用这种方式来消除重复的省结果集。 方式三 LooseScan execution strategy 松散策略

1
2
3
4
5
6

SELECT * 
FROM order_info oi
WHERE order_id IN (
    SELECT order_id FROM deliver_bill db WHERE db.order_id LIKE 'XXX'
)
# deliver_bill 中 order_id 是二级索引

那么在执行子查询查发货单表的时候，由于 order_id 模糊查询，而且在发货单中可能存在很多重复的记录，那么在使用发货单二级索引的时候，就可以直接跳过这些重复的订单号值，拿到不重复的值就可以了。 方式四 Semi-join Materialization execution strategy 这是上面临时表策略 方式五 FirstMatch execution strategy 匹配字表跳出字表查询 从外表取出记录去一次一次匹配字表的记录，是一种最原始的方式。如果这条记录已经满足了条件，那么假如结果集，不再去匹配子表而是回到外表，继续下一条记录。

图来自 semi-join子查询优化 – FirstMatch策略

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。

那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引，先拿到 id，然后再去缓存命中，再走数据库~

单列聚簇索引还有个需要注意的点，就是这个列的辨识度要搞，如果这个列只有 MAN 和 WOMAN 的话，为这个列建立索引根本就没有什么用处，因为跟全表扫描一样的效率，优化器更偏向于全表扫描，所以切记不要给列值只有寥寥几个的列建立索引，纯属浪费。

5.2 多列非聚簇索引

如果是 name + mobile 联合索引的话，需要注意的点就有点多了：

每个数据页的排序就会变成，先按照 name 进行排序，然后再按照 mobile 进行排序。

5.4 什么时候不会使用索引

1.不满足最左匹配

我想大家都听过 最左匹配原则，就是这个意思，因为我的索引是先根据 name 排序再根据 mobile 进行排序的。那么查询的时候，如果加上 order by 的话，这个排序同样也是派上用场的。

但是如果说查询条件只是写了 WHERE mobile = '13800x1'，那上面的索引就完全派不上用场。

怎么说，因为我这个索引是结合了 name 先做排序然后索引的，你只是查询 mobile 的话，就需要遍历整个索引，拿到 id 后还需要回表，这个过程跟直接扫描 聚簇索引 相比，耗费的资源更多，所以，如果一个 name + mobile 的索引，只应用于带有 name 开始的查询条件。因为 name 在前面。这就是 最左匹配原则。

2.排序一个列使用升序一个使用降序

比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC，这样的情况只能用到 name 列的索引（也就是所有 mobile 失去了效果），然后再把所有列重新整理，依据 mobile 重新排序。

如果两个都是同一个方向的排序就不会出现这种情况。

3.VARCHAR 匹配前缀查询

WHERE name like '%狗蛋' 这种情况为什么不能使用索引呢，因为你前面未知啊，根据 name 排序的索引查询跟全表扫描有什么区别，还少了 回表 的操作，所以只能全表扫描，取出满足 xxx狗蛋 的数据了。

4.排序用到索引中没有的列

这个理解了 区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已 这句话，就知道为什么了，因为索引中的排序并不适合 SQL 指定的顺序。

5.使用函数修饰值的时候

比如 WHERE LOWER(name) = 'aa'，每个列都需要通过函数调用，那就跟全表扫描没什么区别了。

那如果 SQL 语句中，条件出现的顺序没有和多列索引的顺序一致的话，会怎么样：

完全不必担心这个问题，因为 SQL 在执行之前还会交给一个叫做 优化器 的东西进行整理，下面会说到，现在就只要知道他会把 SQL 条件整理成跟索引一样的顺序就好了。

既然多列索引可以帮忙查询条件中满足最左匹配的 SQL 语句，是不是越多越好，答案并不是，我觉得应该根据权重来区分，因为 非聚簇索引 他的索引列并不会像自增 ID 的索引树一样，顺序的插入数据（历史原因导致我们项目使用 UUID 做主键的哭晕在厕所），而是经常的造成 页拆分（也就是上面拆分的动图），所以 非聚簇索引 多了，增删改 需要维护这棵树平衡所做的 整容 就越多，严重的话会影响 增删改 的效率。

5.5 什么时候命中索引

那什么时候用到了索引，自然就是避免上面的情况就可以了，就有这些情况，包括但不局限于：

1. 条件覆盖了索引的最左列；
2. 常量查询，WHERE name = 'xxx' ；
3. 范围查询，满足 1 的情况下，比如 name > 'AA' 或者 name = 'AA' AND mobile > '13800';
4. 排序，但是需要用到的排序列是同一个方向进行排序的。
5. 分组，依然需要满足 1 条件，如果用到了 group by name，InnoDB 会先将相同的 name 放在一起，然后再继续根据其他条件进行运算。

5.6 回表代价

可以这么说，如果回表的代价过高，InnoDB解析器 可能直接决定，不要使用索引，直接全表扫描。

怎么回事，就是 非聚簇 索引他的值都是连在一起的，查询的时候，称为 顺序I/O，而 非聚簇索引 查询出来的 id 并不会连在一起，所以回表去查询 id 数据的时候，称为 随机I/O。而 随机I/O 的效率是很低的，所以当命中索引的数据行总是较多的时候，不如 全表扫描 来的快，所以可能出现 SQL 已经完全命中这个索引但是解析器他就是不使用。

怎么防止这种情况发生，就是让查询索引返回的数量少，比如我们可以 LIMIT 100 去限定只查询 100 条数据，或者我们只要查询索引中出现的列，比如 id 然后再在程序中，根据 id 列表去命中缓存，名不中的再一次性批量查库就可以了。

5.7 文件排序

有时候我们去解析 EXPLAIN 我们的 SQL 语句的时候，会出现 File Sort 类型，这个类型指的是，查询出来的结果不是按照我们 SQL 指定的顺序来的，所以需要在内存中（必要时借助硬盘）来重新对数据进行排序，这个过程就是 File Sort，那如何避免这个类型出现，那就是防止上面不命中索引的情况。

5.8 索引合并

使用等值且命中两个索引的列

比方说我的用户表有 name 索引 和 mobile 索引，那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777' 就可以使用两个索引，然后取 id 的 交集，然后回表查询。但是如果 name > 'Weidan' 这种条件，就不会使用到合并。

但是但是，如果是主键列是范围的话，是可以的，因为他们合并的时候也会操作主键嘛。

不过有没有使用到，还要看成本，如果一个索引命中的数据太多，依然不会使用合并索引。

合并两个索引的列

依然需要满足 列都是等值查询 这个条件，比如 WHERE name = 'Weidan' OR mobile = '18588777777'，会合并两个主键再统一回表查询。

范围搜索合并查询

不过如果我们是范围查询，又想使用两个索引怎么办，我们可以把 name > 'Weidan' 以及 monile > '18588777777' 先查询出来 id 然后 union 在一起，再通过 id 去寻找我们想要的数据。

但是还是建议把需要合并的列作为一个 非聚簇 索引来覆盖，效率要高。

七.表连接查询

首先就以最经典的学生、成绩来做示例吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CREATE TABLE `student` (
  `id` int(11) NOT NULL,
  `name` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `student` VALUES (1, '狗蛋');
INSERT INTO `student` VALUES (2, '狗剩');
INSERT INTO `student` VALUES (3, '翠花');
COMMIT;

DROP TABLE IF EXISTS `scope`;
CREATE TABLE `scope` (
  `id` int(11) NOT NULL,
  `subject` varchar(255) DEFAULT NULL,
  `scope` int(255) DEFAULT NULL,
  `stu_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `scope` VALUES (1, '语文', 80, 1);
INSERT INTO `scope` VALUES (2, '数学', 98, 1);
INSERT INTO `scope` VALUES (3, '英语', 59, 2);
INSERT INTO `scope` VALUES (4, '政治', 79, 2);
COMMIT;

7.1 连表查询

那么先列举一个连表很普通的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT * 
FROM student, scope;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  2 | 狗剩   |  1 | 语文    |    80 |      1 |
|  3 | 翠花   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  2 | 数学    |    98 |      1 |
|  3 | 翠花   |  2 | 数学    |    98 |      1 |
|  1 | 狗蛋   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  3 | 翠花   |  3 | 英语    |    59 |      2 |
|  1 | 狗蛋   |  4 | 政治    |    79 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
|  3 | 翠花   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
12 rows in set (0.00 sec)

可以看到，如果我们不加任何条件，直接就连接两张表的话，取出来的结果就是第一张表所有的数据，去搭配第二张表所有的数据，也就是第一张表有 3 条数据，第二张表有 4 条记录，结果就有 3 ✖ 4 = 12 条记录。这个过程也称为 笛卡尔积。这种情况在日常编程中应该也没人会这么写的吧，仔细想想，如果两张表都是百万级别的数据，笛卡尔积是多恐怖的一件事情。

7.2 内连接

就是由于上面的结果集一般我们都不需要，所以我们会加上一些条件加以限制：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
4 rows in set (0.00 sec)

这就是我们想要的结果集，所有参考学生的考试成绩。

而 InnoDB 是怎样的实现两个表连接的呢，这时候，优化器会根据查询成本确定 驱动表 和 被驱动表。

• 驱动表：先查询的那个表，这里假设是 student 表，所以执行的时候，第一步执行 SELECT * FROM student;；

• 被驱动表：查询出来驱动表所有的数据以后，就会根据驱动表中每一条数据，去执行被驱动表。

  • 比如我现在 student 有三条记录，分别 id 是 1 2 3；
  • 然后对三条记录分别执行 SELECT * FROM scope WHERE stu_id = ?；
  • 因为 scope 表中不存在 翠花 的成绩，所以 SELECT * FROM scope WHERE stu_id = 3 并没有展示出来，因为这个语句相当于 SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3

那如果上面的语句加上其他条件会怎么样，比如：

1
2
3
4
5

# 查询成绩 90 分以上的学生成绩信息
SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id
  AND scp.scope > 90;

那在访问驱动表 student 的时候同上面一样，但是针对驱动表中每一条数据执行被驱动表的时候，就会变成：

SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;

一句话就是说，这些条件针对哪个表，在执行那个表的时候就会带上指定的条件。

内连接推荐写法：

1
2
3

SELECT stu.*, scp.*
FROM student stu INNER JOIN scope scp ON stu.id = scp.stu_id
WHERE scp.scope > 90;

效率没有变高，但是可读性变好，在我看来，特定的限定功能就需要放在特定的位置，连接条件在 ON 后面，而查询条件在 WHERE 后面，也可以很好的跟下面的外连接写法统一。

7.3 外连接

外连接的目的是将连接在一起查询的表中，以某个表为主要目的，查询他在另外一个表的所有信息，包括不存在的信息。比如还是上面的例子，翠花她是个坏学生，一个科目都没有参加考试，但是老师如果通过上面的内连接查询来看的话，可能都不知道还有这个人的存在。这就麻烦大了啊，家长上门投诉，我给你钱了，她没参加考试你都不管管的吗。所以这时候，就需要外连接来做这个事情了：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
+----+--------+------+---------+-------+--------+
| id | name   | id   | subject | scope | stu_id |
+----+--------+------+---------+-------+--------+
|  1 | 狗蛋   |    1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |    2 | 数学    |    98 |      1 |
|  2 | 狗剩   |    3 | 英语    |    59 |      2 |
|  2 | 狗剩   |    4 | 政治    |    79 |      2 |
|  3 | 翠花   | NULL | NULL    |  NULL |   NULL |
+----+--------+------+---------+-------+--------+
5 rows in set (0.00 sec)			

这个时候，嗯哼，一抓一个准，没有来考试的，在 scope 表的字段中，显示为 NULL。

关于 驱动表 和 被驱动表 的含义已经在上面内连接的内容中指定，那么如果说 内连接 是根据成本来指定 驱动表 的，那 外连接 就是我们来指定驱动表。

以 驱动表 所有满足我们条件的数据，来查询 被驱动表，如果 被驱动表 不存在 驱动表 中某条数据的关联，显示为 NULL。

那么关键点在哪里，就在这个 ON 后面的条件，ON 后面的条件，是指定 被驱动表 中不满足 ON 条件情况下依然要显示的关键。（在内连接中连接条件放 ON 和放 WHERE 效果一样）

如果外连接有几层，比如说三层：

1
2
3
4

SELECT *
FROM teacher t
  LEFT JOIN student ON t.id = stu.into
  LEFT JOIN scope scp ON stu.id = scope.stu_id;

那么上面这条查询需要怎么走呢，先查询老师所有的学生，得到一张中间表以后，再以这张中间表作为 驱动表 来查询 scope。

八.复杂条件查询

MySQL InnoDB 中存在着 SQL解析器，解析器可谓为了查询正确的数据而费尽心思，目的只有一个，就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器，为了执行效率比较快，会对字节码进行一些顺序的重新编排，什么 happen before 规则都出来了。

而什么东西查询最快呢，那就是查询常量的时候了。

8.1 整理查询语句

首先就是去除不必要的括号，因为括号如果没有意义存在，那移除了就更有利于优化器的解析了。

比如 WHERE (id = 1) 会被优化成 WHERE id = 1。这个好像也没什么好说的。

复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20 则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20。

8.2 简化查询条件

WHERE age > 18 AND real_age > age 则直接变成 WHERE age > 18 AND real_age > 18

8.3 删除废话条件

像我之前老师教的，在写 MyBatis Mapper.xml 的时候，因为 WHERE 总是需要动态的条件，所以前面会加一个 WHERE 1 = 1（为啥不用标签，因为标签可读性其实不怎么高）。

那么，如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'，那么语句将会被直接优化为 WHERE name LIKE 'Weidan%' 。这么想想好像直接写 WHERE 1 = 1 除了解析器多了点工作，好像也没什么所谓了。

8.4 计算表达式

WHERE age = 9 + 9 那么解析器会直接给你个 WHERE age = 18。不过如果这些计算方式放在了列名上，比如：

1
2

WHERE -age = -18
WHERE to_days(age) = 18

解析器害怕他也优化错了，所以也会放弃优化，一个简单的记忆就是函数发生在等号后面的常量值上，可以优化，但是如果需要依赖列的计算的话，那就放弃优化了。

8.5 必要时转换外连接到内连接

右外连接会被转换为左外连接，毕竟 左外连接 更好确定 驱动表 和 被驱动表。

那如果我们在查询 左外连接 的时候，暗示着我得出的结果中，被驱动表不含 NULL 的值，聪明的暖男解析器将会 GET 到这个信息，把 外连接 优化成 内连接。

比如上面的例子中：

1
2
3
4
5
6
7

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
  AND scp.id IS NOT NULL;

那么上面两个语句中是不是就都暗示解析器中，拿到的 scope 中的 id 不能为空。

所以！直接变成这条语句执行：

1
2
3
4
5
6

SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id;;

九.完

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。

那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引，先拿到 id，然后再去缓存命中，再走数据库~

单列聚簇索引还有个需要注意的点，就是这个列的辨识度要搞，如果这个列只有 MAN 和 WOMAN 的话，为这个列建立索引根本就没有什么用处，因为跟全表扫描一样的效率，优化器更偏向于全表扫描，所以切记不要给列值只有寥寥几个的列建立索引，纯属浪费。

5.2 多列非聚簇索引

如果是 name + mobile 联合索引的话，需要注意的点就有点多了：

每个数据页的排序就会变成，先按照 name 进行排序，然后再按照 mobile 进行排序。

5.4 什么时候不会使用索引

1.不满足最左匹配

我想大家都听过 最左匹配原则，就是这个意思，因为我的索引是先根据 name 排序再根据 mobile 进行排序的。那么查询的时候，如果加上 order by 的话，这个排序同样也是派上用场的。

但是如果说查询条件只是写了 WHERE mobile = '13800x1'，那上面的索引就完全派不上用场。

怎么说，因为我这个索引是结合了 name 先做排序然后索引的，你只是查询 mobile 的话，就需要遍历整个索引，拿到 id 后还需要回表，这个过程跟直接扫描 聚簇索引 相比，耗费的资源更多，所以，如果一个 name + mobile 的索引，只应用于带有 name 开始的查询条件。因为 name 在前面。这就是 最左匹配原则。

2.排序一个列使用升序一个使用降序

比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC，这样的情况只能用到 name 列的索引（也就是所有 mobile 失去了效果），然后再把所有列重新整理，依据 mobile 重新排序。

如果两个都是同一个方向的排序就不会出现这种情况。

3.VARCHAR 匹配前缀查询

WHERE name like '%狗蛋' 这种情况为什么不能使用索引呢，因为你前面未知啊，根据 name 排序的索引查询跟全表扫描有什么区别，还少了 回表 的操作，所以只能全表扫描，取出满足 xxx狗蛋 的数据了。

4.排序用到索引中没有的列

这个理解了 区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已 这句话，就知道为什么了，因为索引中的排序并不适合 SQL 指定的顺序。

5.使用函数修饰值的时候

比如 WHERE LOWER(name) = 'aa'，每个列都需要通过函数调用，那就跟全表扫描没什么区别了。

那如果 SQL 语句中，条件出现的顺序没有和多列索引的顺序一致的话，会怎么样：

完全不必担心这个问题，因为 SQL 在执行之前还会交给一个叫做 优化器 的东西进行整理，下面会说到，现在就只要知道他会把 SQL 条件整理成跟索引一样的顺序就好了。

既然多列索引可以帮忙查询条件中满足最左匹配的 SQL 语句，是不是越多越好，答案并不是，我觉得应该根据权重来区分，因为 非聚簇索引 他的索引列并不会像自增 ID 的索引树一样，顺序的插入数据（历史原因导致我们项目使用 UUID 做主键的哭晕在厕所），而是经常的造成 页拆分（也就是上面拆分的动图），所以 非聚簇索引 多了，增删改 需要维护这棵树平衡所做的 整容 就越多，严重的话会影响 增删改 的效率。

5.5 什么时候命中索引

那什么时候用到了索引，自然就是避免上面的情况就可以了，就有这些情况，包括但不局限于：

1. 条件覆盖了索引的最左列；
2. 常量查询，WHERE name = 'xxx' ；
3. 范围查询，满足 1 的情况下，比如 name > 'AA' 或者 name = 'AA' AND mobile > '13800';
4. 排序，但是需要用到的排序列是同一个方向进行排序的。
5. 分组，依然需要满足 1 条件，如果用到了 group by name，InnoDB 会先将相同的 name 放在一起，然后再继续根据其他条件进行运算。

5.6 回表代价

可以这么说，如果回表的代价过高，InnoDB解析器 可能直接决定，不要使用索引，直接全表扫描。

怎么回事，就是 非聚簇 索引他的值都是连在一起的，查询的时候，称为 顺序I/O，而 非聚簇索引 查询出来的 id 并不会连在一起，所以回表去查询 id 数据的时候，称为 随机I/O。而 随机I/O 的效率是很低的，所以当命中索引的数据行总是较多的时候，不如 全表扫描 来的快，所以可能出现 SQL 已经完全命中这个索引但是解析器他就是不使用。

怎么防止这种情况发生，就是让查询索引返回的数量少，比如我们可以 LIMIT 100 去限定只查询 100 条数据，或者我们只要查询索引中出现的列，比如 id 然后再在程序中，根据 id 列表去命中缓存，名不中的再一次性批量查库就可以了。

5.7 文件排序

有时候我们去解析 EXPLAIN 我们的 SQL 语句的时候，会出现 File Sort 类型，这个类型指的是，查询出来的结果不是按照我们 SQL 指定的顺序来的，所以需要在内存中（必要时借助硬盘）来重新对数据进行排序，这个过程就是 File Sort，那如何避免这个类型出现，那就是防止上面不命中索引的情况。

5.8 索引合并

使用等值且命中两个索引的列

比方说我的用户表有 name 索引 和 mobile 索引，那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777' 就可以使用两个索引，然后取 id 的 交集，然后回表查询。但是如果 name > 'Weidan' 这种条件，就不会使用到合并。

但是但是，如果是主键列是范围的话，是可以的，因为他们合并的时候也会操作主键嘛。

不过有没有使用到，还要看成本，如果一个索引命中的数据太多，依然不会使用合并索引。

合并两个索引的列

依然需要满足 列都是等值查询 这个条件，比如 WHERE name = 'Weidan' OR mobile = '18588777777'，会合并两个主键再统一回表查询。

范围搜索合并查询

不过如果我们是范围查询，又想使用两个索引怎么办，我们可以把 name > 'Weidan' 以及 monile > '18588777777' 先查询出来 id 然后 union 在一起，再通过 id 去寻找我们想要的数据。

但是还是建议把需要合并的列作为一个 非聚簇 索引来覆盖，效率要高。

七.表连接查询

首先就以最经典的学生、成绩来做示例吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CREATE TABLE `student` (
  `id` int(11) NOT NULL,
  `name` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `student` VALUES (1, '狗蛋');
INSERT INTO `student` VALUES (2, '狗剩');
INSERT INTO `student` VALUES (3, '翠花');
COMMIT;

DROP TABLE IF EXISTS `scope`;
CREATE TABLE `scope` (
  `id` int(11) NOT NULL,
  `subject` varchar(255) DEFAULT NULL,
  `scope` int(255) DEFAULT NULL,
  `stu_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `scope` VALUES (1, '语文', 80, 1);
INSERT INTO `scope` VALUES (2, '数学', 98, 1);
INSERT INTO `scope` VALUES (3, '英语', 59, 2);
INSERT INTO `scope` VALUES (4, '政治', 79, 2);
COMMIT;

7.1 连表查询

那么先列举一个连表很普通的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT * 
FROM student, scope;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  2 | 狗剩   |  1 | 语文    |    80 |      1 |
|  3 | 翠花   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  2 | 数学    |    98 |      1 |
|  3 | 翠花   |  2 | 数学    |    98 |      1 |
|  1 | 狗蛋   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  3 | 翠花   |  3 | 英语    |    59 |      2 |
|  1 | 狗蛋   |  4 | 政治    |    79 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
|  3 | 翠花   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
12 rows in set (0.00 sec)

可以看到，如果我们不加任何条件，直接就连接两张表的话，取出来的结果就是第一张表所有的数据，去搭配第二张表所有的数据，也就是第一张表有 3 条数据，第二张表有 4 条记录，结果就有 3 ✖ 4 = 12 条记录。这个过程也称为 笛卡尔积。这种情况在日常编程中应该也没人会这么写的吧，仔细想想，如果两张表都是百万级别的数据，笛卡尔积是多恐怖的一件事情。

7.2 内连接

就是由于上面的结果集一般我们都不需要，所以我们会加上一些条件加以限制：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
4 rows in set (0.00 sec)

这就是我们想要的结果集，所有参考学生的考试成绩。

而 InnoDB 是怎样的实现两个表连接的呢，这时候，优化器会根据查询成本确定 驱动表 和 被驱动表。

• 驱动表：先查询的那个表，这里假设是 student 表，所以执行的时候，第一步执行 SELECT * FROM student;；

• 被驱动表：查询出来驱动表所有的数据以后，就会根据驱动表中每一条数据，去执行被驱动表。

  • 比如我现在 student 有三条记录，分别 id 是 1 2 3；
  • 然后对三条记录分别执行 SELECT * FROM scope WHERE stu_id = ?；
  • 因为 scope 表中不存在 翠花 的成绩，所以 SELECT * FROM scope WHERE stu_id = 3 并没有展示出来，因为这个语句相当于 SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3

那如果上面的语句加上其他条件会怎么样，比如：

1
2
3
4
5

# 查询成绩 90 分以上的学生成绩信息
SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id
  AND scp.scope > 90;

那在访问驱动表 student 的时候同上面一样，但是针对驱动表中每一条数据执行被驱动表的时候，就会变成：

SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;

一句话就是说，这些条件针对哪个表，在执行那个表的时候就会带上指定的条件。

内连接推荐写法：

1
2
3

SELECT stu.*, scp.*
FROM student stu INNER JOIN scope scp ON stu.id = scp.stu_id
WHERE scp.scope > 90;

效率没有变高，但是可读性变好，在我看来，特定的限定功能就需要放在特定的位置，连接条件在 ON 后面，而查询条件在 WHERE 后面，也可以很好的跟下面的外连接写法统一。

7.3 外连接

外连接的目的是将连接在一起查询的表中，以某个表为主要目的，查询他在另外一个表的所有信息，包括不存在的信息。比如还是上面的例子，翠花她是个坏学生，一个科目都没有参加考试，但是老师如果通过上面的内连接查询来看的话，可能都不知道还有这个人的存在。这就麻烦大了啊，家长上门投诉，我给你钱了，她没参加考试你都不管管的吗。所以这时候，就需要外连接来做这个事情了：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
+----+--------+------+---------+-------+--------+
| id | name   | id   | subject | scope | stu_id |
+----+--------+------+---------+-------+--------+
|  1 | 狗蛋   |    1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |    2 | 数学    |    98 |      1 |
|  2 | 狗剩   |    3 | 英语    |    59 |      2 |
|  2 | 狗剩   |    4 | 政治    |    79 |      2 |
|  3 | 翠花   | NULL | NULL    |  NULL |   NULL |
+----+--------+------+---------+-------+--------+
5 rows in set (0.00 sec)			

这个时候，嗯哼，一抓一个准，没有来考试的，在 scope 表的字段中，显示为 NULL。

关于 驱动表 和 被驱动表 的含义已经在上面内连接的内容中指定，那么如果说 内连接 是根据成本来指定 驱动表 的，那 外连接 就是我们来指定驱动表。

以 驱动表 所有满足我们条件的数据，来查询 被驱动表，如果 被驱动表 不存在 驱动表 中某条数据的关联，显示为 NULL。

那么关键点在哪里，就在这个 ON 后面的条件，ON 后面的条件，是指定 被驱动表 中不满足 ON 条件情况下依然要显示的关键。（在内连接中连接条件放 ON 和放 WHERE 效果一样）

如果外连接有几层，比如说三层：

1
2
3
4

SELECT *
FROM teacher t
  LEFT JOIN student ON t.id = stu.into
  LEFT JOIN scope scp ON stu.id = scope.stu_id;

那么上面这条查询需要怎么走呢，先查询老师所有的学生，得到一张中间表以后，再以这张中间表作为 驱动表 来查询 scope。

八.复杂条件查询

MySQL InnoDB 中存在着 SQL解析器，解析器可谓为了查询正确的数据而费尽心思，目的只有一个，就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器，为了执行效率比较快，会对字节码进行一些顺序的重新编排，什么 happen before 规则都出来了。

而什么东西查询最快呢，那就是查询常量的时候了。

8.1 整理查询语句

首先就是去除不必要的括号，因为括号如果没有意义存在，那移除了就更有利于优化器的解析了。

比如 WHERE (id = 1) 会被优化成 WHERE id = 1。这个好像也没什么好说的。

复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20 则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20。

8.2 简化查询条件

WHERE age > 18 AND real_age > age 则直接变成 WHERE age > 18 AND real_age > 18

8.3 删除废话条件

像我之前老师教的，在写 MyBatis Mapper.xml 的时候，因为 WHERE 总是需要动态的条件，所以前面会加一个 WHERE 1 = 1（为啥不用标签，因为标签可读性其实不怎么高）。

那么，如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'，那么语句将会被直接优化为 WHERE name LIKE 'Weidan%' 。这么想想好像直接写 WHERE 1 = 1 除了解析器多了点工作，好像也没什么所谓了。

8.4 计算表达式

WHERE age = 9 + 9 那么解析器会直接给你个 WHERE age = 18。不过如果这些计算方式放在了列名上，比如：

1
2

WHERE -age = -18
WHERE to_days(age) = 18

解析器害怕他也优化错了，所以也会放弃优化，一个简单的记忆就是函数发生在等号后面的常量值上，可以优化，但是如果需要依赖列的计算的话，那就放弃优化了。

8.5 必要时转换外连接到内连接

右外连接会被转换为左外连接，毕竟 左外连接 更好确定 驱动表 和 被驱动表。

那如果我们在查询 左外连接 的时候，暗示着我得出的结果中，被驱动表不含 NULL 的值，聪明的暖男解析器将会 GET 到这个信息，把 外连接 优化成 内连接。

比如上面的例子中：

1
2
3
4
5
6
7

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
  AND scp.id IS NOT NULL;

那么上面两个语句中是不是就都暗示解析器中，拿到的 scope 中的 id 不能为空。

所以！直接变成这条语句执行：

1
2
3
4
5
6

SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id;;

九.完

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。

那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引，先拿到 id，然后再去缓存命中，再走数据库~

单列聚簇索引还有个需要注意的点，就是这个列的辨识度要搞，如果这个列只有 MAN 和 WOMAN 的话，为这个列建立索引根本就没有什么用处，因为跟全表扫描一样的效率，优化器更偏向于全表扫描，所以切记不要给列值只有寥寥几个的列建立索引，纯属浪费。

5.2 多列非聚簇索引

如果是 name + mobile 联合索引的话，需要注意的点就有点多了：

每个数据页的排序就会变成，先按照 name 进行排序，然后再按照 mobile 进行排序。

5.4 什么时候不会使用索引

1.不满足最左匹配

我想大家都听过 最左匹配原则，就是这个意思，因为我的索引是先根据 name 排序再根据 mobile 进行排序的。那么查询的时候，如果加上 order by 的话，这个排序同样也是派上用场的。

但是如果说查询条件只是写了 WHERE mobile = '13800x1'，那上面的索引就完全派不上用场。

怎么说，因为我这个索引是结合了 name 先做排序然后索引的，你只是查询 mobile 的话，就需要遍历整个索引，拿到 id 后还需要回表，这个过程跟直接扫描 聚簇索引 相比，耗费的资源更多，所以，如果一个 name + mobile 的索引，只应用于带有 name 开始的查询条件。因为 name 在前面。这就是 最左匹配原则。

2.排序一个列使用升序一个使用降序

比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC，这样的情况只能用到 name 列的索引（也就是所有 mobile 失去了效果），然后再把所有列重新整理，依据 mobile 重新排序。

如果两个都是同一个方向的排序就不会出现这种情况。

3.VARCHAR 匹配前缀查询

WHERE name like '%狗蛋' 这种情况为什么不能使用索引呢，因为你前面未知啊，根据 name 排序的索引查询跟全表扫描有什么区别，还少了 回表 的操作，所以只能全表扫描，取出满足 xxx狗蛋 的数据了。

4.排序用到索引中没有的列

这个理解了 区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已 这句话，就知道为什么了，因为索引中的排序并不适合 SQL 指定的顺序。

5.使用函数修饰值的时候

比如 WHERE LOWER(name) = 'aa'，每个列都需要通过函数调用，那就跟全表扫描没什么区别了。

那如果 SQL 语句中，条件出现的顺序没有和多列索引的顺序一致的话，会怎么样：

完全不必担心这个问题，因为 SQL 在执行之前还会交给一个叫做 优化器 的东西进行整理，下面会说到，现在就只要知道他会把 SQL 条件整理成跟索引一样的顺序就好了。

既然多列索引可以帮忙查询条件中满足最左匹配的 SQL 语句，是不是越多越好，答案并不是，我觉得应该根据权重来区分，因为 非聚簇索引 他的索引列并不会像自增 ID 的索引树一样，顺序的插入数据（历史原因导致我们项目使用 UUID 做主键的哭晕在厕所），而是经常的造成 页拆分（也就是上面拆分的动图），所以 非聚簇索引 多了，增删改 需要维护这棵树平衡所做的 整容 就越多，严重的话会影响 增删改 的效率。

5.5 什么时候命中索引

那什么时候用到了索引，自然就是避免上面的情况就可以了，就有这些情况，包括但不局限于：

1. 条件覆盖了索引的最左列；
2. 常量查询，WHERE name = 'xxx' ；
3. 范围查询，满足 1 的情况下，比如 name > 'AA' 或者 name = 'AA' AND mobile > '13800';
4. 排序，但是需要用到的排序列是同一个方向进行排序的。
5. 分组，依然需要满足 1 条件，如果用到了 group by name，InnoDB 会先将相同的 name 放在一起，然后再继续根据其他条件进行运算。

5.6 回表代价

可以这么说，如果回表的代价过高，InnoDB解析器 可能直接决定，不要使用索引，直接全表扫描。

怎么回事，就是 非聚簇 索引他的值都是连在一起的，查询的时候，称为 顺序I/O，而 非聚簇索引 查询出来的 id 并不会连在一起，所以回表去查询 id 数据的时候，称为 随机I/O。而 随机I/O 的效率是很低的，所以当命中索引的数据行总是较多的时候，不如 全表扫描 来的快，所以可能出现 SQL 已经完全命中这个索引但是解析器他就是不使用。

怎么防止这种情况发生，就是让查询索引返回的数量少，比如我们可以 LIMIT 100 去限定只查询 100 条数据，或者我们只要查询索引中出现的列，比如 id 然后再在程序中，根据 id 列表去命中缓存，名不中的再一次性批量查库就可以了。

5.7 文件排序

有时候我们去解析 EXPLAIN 我们的 SQL 语句的时候，会出现 File Sort 类型，这个类型指的是，查询出来的结果不是按照我们 SQL 指定的顺序来的，所以需要在内存中（必要时借助硬盘）来重新对数据进行排序，这个过程就是 File Sort，那如何避免这个类型出现，那就是防止上面不命中索引的情况。

5.8 索引合并

使用等值且命中两个索引的列

比方说我的用户表有 name 索引 和 mobile 索引，那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777' 就可以使用两个索引，然后取 id 的 交集，然后回表查询。但是如果 name > 'Weidan' 这种条件，就不会使用到合并。

但是但是，如果是主键列是范围的话，是可以的，因为他们合并的时候也会操作主键嘛。

不过有没有使用到，还要看成本，如果一个索引命中的数据太多，依然不会使用合并索引。

合并两个索引的列

依然需要满足 列都是等值查询 这个条件，比如 WHERE name = 'Weidan' OR mobile = '18588777777'，会合并两个主键再统一回表查询。

范围搜索合并查询

不过如果我们是范围查询，又想使用两个索引怎么办，我们可以把 name > 'Weidan' 以及 monile > '18588777777' 先查询出来 id 然后 union 在一起，再通过 id 去寻找我们想要的数据。

但是还是建议把需要合并的列作为一个 非聚簇 索引来覆盖，效率要高。

七.表连接查询

首先就以最经典的学生、成绩来做示例吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CREATE TABLE `student` (
  `id` int(11) NOT NULL,
  `name` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `student` VALUES (1, '狗蛋');
INSERT INTO `student` VALUES (2, '狗剩');
INSERT INTO `student` VALUES (3, '翠花');
COMMIT;

DROP TABLE IF EXISTS `scope`;
CREATE TABLE `scope` (
  `id` int(11) NOT NULL,
  `subject` varchar(255) DEFAULT NULL,
  `scope` int(255) DEFAULT NULL,
  `stu_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `scope` VALUES (1, '语文', 80, 1);
INSERT INTO `scope` VALUES (2, '数学', 98, 1);
INSERT INTO `scope` VALUES (3, '英语', 59, 2);
INSERT INTO `scope` VALUES (4, '政治', 79, 2);
COMMIT;

7.1 连表查询

那么先列举一个连表很普通的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT * 
FROM student, scope;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  2 | 狗剩   |  1 | 语文    |    80 |      1 |
|  3 | 翠花   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  2 | 数学    |    98 |      1 |
|  3 | 翠花   |  2 | 数学    |    98 |      1 |
|  1 | 狗蛋   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  3 | 翠花   |  3 | 英语    |    59 |      2 |
|  1 | 狗蛋   |  4 | 政治    |    79 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
|  3 | 翠花   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
12 rows in set (0.00 sec)

可以看到，如果我们不加任何条件，直接就连接两张表的话，取出来的结果就是第一张表所有的数据，去搭配第二张表所有的数据，也就是第一张表有 3 条数据，第二张表有 4 条记录，结果就有 3 ✖ 4 = 12 条记录。这个过程也称为 笛卡尔积。这种情况在日常编程中应该也没人会这么写的吧，仔细想想，如果两张表都是百万级别的数据，笛卡尔积是多恐怖的一件事情。

7.2 内连接

就是由于上面的结果集一般我们都不需要，所以我们会加上一些条件加以限制：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
4 rows in set (0.00 sec)

这就是我们想要的结果集，所有参考学生的考试成绩。

而 InnoDB 是怎样的实现两个表连接的呢，这时候，优化器会根据查询成本确定 驱动表 和 被驱动表。

• 驱动表：先查询的那个表，这里假设是 student 表，所以执行的时候，第一步执行 SELECT * FROM student;；

• 被驱动表：查询出来驱动表所有的数据以后，就会根据驱动表中每一条数据，去执行被驱动表。

  • 比如我现在 student 有三条记录，分别 id 是 1 2 3；
  • 然后对三条记录分别执行 SELECT * FROM scope WHERE stu_id = ?；
  • 因为 scope 表中不存在 翠花 的成绩，所以 SELECT * FROM scope WHERE stu_id = 3 并没有展示出来，因为这个语句相当于 SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3

那如果上面的语句加上其他条件会怎么样，比如：

1
2
3
4
5

# 查询成绩 90 分以上的学生成绩信息
SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id
  AND scp.scope > 90;

那在访问驱动表 student 的时候同上面一样，但是针对驱动表中每一条数据执行被驱动表的时候，就会变成：

SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;

一句话就是说，这些条件针对哪个表，在执行那个表的时候就会带上指定的条件。

内连接推荐写法：

1
2
3

SELECT stu.*, scp.*
FROM student stu INNER JOIN scope scp ON stu.id = scp.stu_id
WHERE scp.scope > 90;

效率没有变高，但是可读性变好，在我看来，特定的限定功能就需要放在特定的位置，连接条件在 ON 后面，而查询条件在 WHERE 后面，也可以很好的跟下面的外连接写法统一。

7.3 外连接

外连接的目的是将连接在一起查询的表中，以某个表为主要目的，查询他在另外一个表的所有信息，包括不存在的信息。比如还是上面的例子，翠花她是个坏学生，一个科目都没有参加考试，但是老师如果通过上面的内连接查询来看的话，可能都不知道还有这个人的存在。这就麻烦大了啊，家长上门投诉，我给你钱了，她没参加考试你都不管管的吗。所以这时候，就需要外连接来做这个事情了：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
+----+--------+------+---------+-------+--------+
| id | name   | id   | subject | scope | stu_id |
+----+--------+------+---------+-------+--------+
|  1 | 狗蛋   |    1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |    2 | 数学    |    98 |      1 |
|  2 | 狗剩   |    3 | 英语    |    59 |      2 |
|  2 | 狗剩   |    4 | 政治    |    79 |      2 |
|  3 | 翠花   | NULL | NULL    |  NULL |   NULL |
+----+--------+------+---------+-------+--------+
5 rows in set (0.00 sec)			

这个时候，嗯哼，一抓一个准，没有来考试的，在 scope 表的字段中，显示为 NULL。

关于 驱动表 和 被驱动表 的含义已经在上面内连接的内容中指定，那么如果说 内连接 是根据成本来指定 驱动表 的，那 外连接 就是我们来指定驱动表。

以 驱动表 所有满足我们条件的数据，来查询 被驱动表，如果 被驱动表 不存在 驱动表 中某条数据的关联，显示为 NULL。

那么关键点在哪里，就在这个 ON 后面的条件，ON 后面的条件，是指定 被驱动表 中不满足 ON 条件情况下依然要显示的关键。（在内连接中连接条件放 ON 和放 WHERE 效果一样）

如果外连接有几层，比如说三层：

1
2
3
4

SELECT *
FROM teacher t
  LEFT JOIN student ON t.id = stu.into
  LEFT JOIN scope scp ON stu.id = scope.stu_id;

那么上面这条查询需要怎么走呢，先查询老师所有的学生，得到一张中间表以后，再以这张中间表作为 驱动表 来查询 scope。

八.复杂条件查询

MySQL InnoDB 中存在着 SQL解析器，解析器可谓为了查询正确的数据而费尽心思，目的只有一个，就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器，为了执行效率比较快，会对字节码进行一些顺序的重新编排，什么 happen before 规则都出来了。

而什么东西查询最快呢，那就是查询常量的时候了。

8.1 整理查询语句

首先就是去除不必要的括号，因为括号如果没有意义存在，那移除了就更有利于优化器的解析了。

比如 WHERE (id = 1) 会被优化成 WHERE id = 1。这个好像也没什么好说的。

复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20 则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20。

8.2 简化查询条件

WHERE age > 18 AND real_age > age 则直接变成 WHERE age > 18 AND real_age > 18

8.3 删除废话条件

像我之前老师教的，在写 MyBatis Mapper.xml 的时候，因为 WHERE 总是需要动态的条件，所以前面会加一个 WHERE 1 = 1（为啥不用标签，因为标签可读性其实不怎么高）。

那么，如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'，那么语句将会被直接优化为 WHERE name LIKE 'Weidan%' 。这么想想好像直接写 WHERE 1 = 1 除了解析器多了点工作，好像也没什么所谓了。

8.4 计算表达式

WHERE age = 9 + 9 那么解析器会直接给你个 WHERE age = 18。不过如果这些计算方式放在了列名上，比如：

1
2

WHERE -age = -18
WHERE to_days(age) = 18

解析器害怕他也优化错了，所以也会放弃优化，一个简单的记忆就是函数发生在等号后面的常量值上，可以优化，但是如果需要依赖列的计算的话，那就放弃优化了。

8.5 必要时转换外连接到内连接

右外连接会被转换为左外连接，毕竟 左外连接 更好确定 驱动表 和 被驱动表。

那如果我们在查询 左外连接 的时候，暗示着我得出的结果中，被驱动表不含 NULL 的值，聪明的暖男解析器将会 GET 到这个信息，把 外连接 优化成 内连接。

比如上面的例子中：

1
2
3
4
5
6
7

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
  AND scp.id IS NOT NULL;

那么上面两个语句中是不是就都暗示解析器中，拿到的 scope 中的 id 不能为空。

所以！直接变成这条语句执行：

1
2
3
4
5
6

SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id;;

九.完

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。

那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引，先拿到 id，然后再去缓存命中，再走数据库~

单列聚簇索引还有个需要注意的点，就是这个列的辨识度要搞，如果这个列只有 MAN 和 WOMAN 的话，为这个列建立索引根本就没有什么用处，因为跟全表扫描一样的效率，优化器更偏向于全表扫描，所以切记不要给列值只有寥寥几个的列建立索引，纯属浪费。

5.2 多列非聚簇索引

如果是 name + mobile 联合索引的话，需要注意的点就有点多了：

每个数据页的排序就会变成，先按照 name 进行排序，然后再按照 mobile 进行排序。

5.4 什么时候不会使用索引

1.不满足最左匹配

我想大家都听过 最左匹配原则，就是这个意思，因为我的索引是先根据 name 排序再根据 mobile 进行排序的。那么查询的时候，如果加上 order by 的话，这个排序同样也是派上用场的。

但是如果说查询条件只是写了 WHERE mobile = '13800x1'，那上面的索引就完全派不上用场。

怎么说，因为我这个索引是结合了 name 先做排序然后索引的，你只是查询 mobile 的话，就需要遍历整个索引，拿到 id 后还需要回表，这个过程跟直接扫描 聚簇索引 相比，耗费的资源更多，所以，如果一个 name + mobile 的索引，只应用于带有 name 开始的查询条件。因为 name 在前面。这就是 最左匹配原则。

2.排序一个列使用升序一个使用降序

比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC，这样的情况只能用到 name 列的索引（也就是所有 mobile 失去了效果），然后再把所有列重新整理，依据 mobile 重新排序。

如果两个都是同一个方向的排序就不会出现这种情况。

3.VARCHAR 匹配前缀查询

WHERE name like '%狗蛋' 这种情况为什么不能使用索引呢，因为你前面未知啊，根据 name 排序的索引查询跟全表扫描有什么区别，还少了 回表 的操作，所以只能全表扫描，取出满足 xxx狗蛋 的数据了。

4.排序用到索引中没有的列

这个理解了 区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已 这句话，就知道为什么了，因为索引中的排序并不适合 SQL 指定的顺序。

5.使用函数修饰值的时候

比如 WHERE LOWER(name) = 'aa'，每个列都需要通过函数调用，那就跟全表扫描没什么区别了。

那如果 SQL 语句中，条件出现的顺序没有和多列索引的顺序一致的话，会怎么样：

完全不必担心这个问题，因为 SQL 在执行之前还会交给一个叫做 优化器 的东西进行整理，下面会说到，现在就只要知道他会把 SQL 条件整理成跟索引一样的顺序就好了。

既然多列索引可以帮忙查询条件中满足最左匹配的 SQL 语句，是不是越多越好，答案并不是，我觉得应该根据权重来区分，因为 非聚簇索引 他的索引列并不会像自增 ID 的索引树一样，顺序的插入数据（历史原因导致我们项目使用 UUID 做主键的哭晕在厕所），而是经常的造成 页拆分（也就是上面拆分的动图），所以 非聚簇索引 多了，增删改 需要维护这棵树平衡所做的 整容 就越多，严重的话会影响 增删改 的效率。

5.5 什么时候命中索引

那什么时候用到了索引，自然就是避免上面的情况就可以了，就有这些情况，包括但不局限于：

1. 条件覆盖了索引的最左列；
2. 常量查询，WHERE name = 'xxx' ；
3. 范围查询，满足 1 的情况下，比如 name > 'AA' 或者 name = 'AA' AND mobile > '13800';
4. 排序，但是需要用到的排序列是同一个方向进行排序的。
5. 分组，依然需要满足 1 条件，如果用到了 group by name，InnoDB 会先将相同的 name 放在一起，然后再继续根据其他条件进行运算。

5.6 回表代价

可以这么说，如果回表的代价过高，InnoDB解析器 可能直接决定，不要使用索引，直接全表扫描。

怎么回事，就是 非聚簇 索引他的值都是连在一起的，查询的时候，称为 顺序I/O，而 非聚簇索引 查询出来的 id 并不会连在一起，所以回表去查询 id 数据的时候，称为 随机I/O。而 随机I/O 的效率是很低的，所以当命中索引的数据行总是较多的时候，不如 全表扫描 来的快，所以可能出现 SQL 已经完全命中这个索引但是解析器他就是不使用。

怎么防止这种情况发生，就是让查询索引返回的数量少，比如我们可以 LIMIT 100 去限定只查询 100 条数据，或者我们只要查询索引中出现的列，比如 id 然后再在程序中，根据 id 列表去命中缓存，名不中的再一次性批量查库就可以了。

5.7 文件排序

有时候我们去解析 EXPLAIN 我们的 SQL 语句的时候，会出现 File Sort 类型，这个类型指的是，查询出来的结果不是按照我们 SQL 指定的顺序来的，所以需要在内存中（必要时借助硬盘）来重新对数据进行排序，这个过程就是 File Sort，那如何避免这个类型出现，那就是防止上面不命中索引的情况。

5.8 索引合并

使用等值且命中两个索引的列

比方说我的用户表有 name 索引 和 mobile 索引，那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777' 就可以使用两个索引，然后取 id 的 交集，然后回表查询。但是如果 name > 'Weidan' 这种条件，就不会使用到合并。

但是但是，如果是主键列是范围的话，是可以的，因为他们合并的时候也会操作主键嘛。

不过有没有使用到，还要看成本，如果一个索引命中的数据太多，依然不会使用合并索引。

合并两个索引的列

依然需要满足 列都是等值查询 这个条件，比如 WHERE name = 'Weidan' OR mobile = '18588777777'，会合并两个主键再统一回表查询。

范围搜索合并查询

不过如果我们是范围查询，又想使用两个索引怎么办，我们可以把 name > 'Weidan' 以及 monile > '18588777777' 先查询出来 id 然后 union 在一起，再通过 id 去寻找我们想要的数据。

但是还是建议把需要合并的列作为一个 非聚簇 索引来覆盖，效率要高。

七.表连接查询

首先就以最经典的学生、成绩来做示例吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CREATE TABLE `student` (
  `id` int(11) NOT NULL,
  `name` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `student` VALUES (1, '狗蛋');
INSERT INTO `student` VALUES (2, '狗剩');
INSERT INTO `student` VALUES (3, '翠花');
COMMIT;

DROP TABLE IF EXISTS `scope`;
CREATE TABLE `scope` (
  `id` int(11) NOT NULL,
  `subject` varchar(255) DEFAULT NULL,
  `scope` int(255) DEFAULT NULL,
  `stu_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `scope` VALUES (1, '语文', 80, 1);
INSERT INTO `scope` VALUES (2, '数学', 98, 1);
INSERT INTO `scope` VALUES (3, '英语', 59, 2);
INSERT INTO `scope` VALUES (4, '政治', 79, 2);
COMMIT;

7.1 连表查询

那么先列举一个连表很普通的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT * 
FROM student, scope;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  2 | 狗剩   |  1 | 语文    |    80 |      1 |
|  3 | 翠花   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  2 | 数学    |    98 |      1 |
|  3 | 翠花   |  2 | 数学    |    98 |      1 |
|  1 | 狗蛋   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  3 | 翠花   |  3 | 英语    |    59 |      2 |
|  1 | 狗蛋   |  4 | 政治    |    79 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
|  3 | 翠花   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
12 rows in set (0.00 sec)

可以看到，如果我们不加任何条件，直接就连接两张表的话，取出来的结果就是第一张表所有的数据，去搭配第二张表所有的数据，也就是第一张表有 3 条数据，第二张表有 4 条记录，结果就有 3 ✖ 4 = 12 条记录。这个过程也称为 笛卡尔积。这种情况在日常编程中应该也没人会这么写的吧，仔细想想，如果两张表都是百万级别的数据，笛卡尔积是多恐怖的一件事情。

7.2 内连接

就是由于上面的结果集一般我们都不需要，所以我们会加上一些条件加以限制：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
4 rows in set (0.00 sec)

这就是我们想要的结果集，所有参考学生的考试成绩。

而 InnoDB 是怎样的实现两个表连接的呢，这时候，优化器会根据查询成本确定 驱动表 和 被驱动表。

• 驱动表：先查询的那个表，这里假设是 student 表，所以执行的时候，第一步执行 SELECT * FROM student;；

• 被驱动表：查询出来驱动表所有的数据以后，就会根据驱动表中每一条数据，去执行被驱动表。

  • 比如我现在 student 有三条记录，分别 id 是 1 2 3；
  • 然后对三条记录分别执行 SELECT * FROM scope WHERE stu_id = ?；
  • 因为 scope 表中不存在 翠花 的成绩，所以 SELECT * FROM scope WHERE stu_id = 3 并没有展示出来，因为这个语句相当于 SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3

那如果上面的语句加上其他条件会怎么样，比如：

1
2
3
4
5

# 查询成绩 90 分以上的学生成绩信息
SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id
  AND scp.scope > 90;

那在访问驱动表 student 的时候同上面一样，但是针对驱动表中每一条数据执行被驱动表的时候，就会变成：

SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;

一句话就是说，这些条件针对哪个表，在执行那个表的时候就会带上指定的条件。

内连接推荐写法：

1
2
3

SELECT stu.*, scp.*
FROM student stu INNER JOIN scope scp ON stu.id = scp.stu_id
WHERE scp.scope > 90;

效率没有变高，但是可读性变好，在我看来，特定的限定功能就需要放在特定的位置，连接条件在 ON 后面，而查询条件在 WHERE 后面，也可以很好的跟下面的外连接写法统一。

7.3 外连接

外连接的目的是将连接在一起查询的表中，以某个表为主要目的，查询他在另外一个表的所有信息，包括不存在的信息。比如还是上面的例子，翠花她是个坏学生，一个科目都没有参加考试，但是老师如果通过上面的内连接查询来看的话，可能都不知道还有这个人的存在。这就麻烦大了啊，家长上门投诉，我给你钱了，她没参加考试你都不管管的吗。所以这时候，就需要外连接来做这个事情了：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
+----+--------+------+---------+-------+--------+
| id | name   | id   | subject | scope | stu_id |
+----+--------+------+---------+-------+--------+
|  1 | 狗蛋   |    1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |    2 | 数学    |    98 |      1 |
|  2 | 狗剩   |    3 | 英语    |    59 |      2 |
|  2 | 狗剩   |    4 | 政治    |    79 |      2 |
|  3 | 翠花   | NULL | NULL    |  NULL |   NULL |
+----+--------+------+---------+-------+--------+
5 rows in set (0.00 sec)			

这个时候，嗯哼，一抓一个准，没有来考试的，在 scope 表的字段中，显示为 NULL。

关于 驱动表 和 被驱动表 的含义已经在上面内连接的内容中指定，那么如果说 内连接 是根据成本来指定 驱动表 的，那 外连接 就是我们来指定驱动表。

以 驱动表 所有满足我们条件的数据，来查询 被驱动表，如果 被驱动表 不存在 驱动表 中某条数据的关联，显示为 NULL。

那么关键点在哪里，就在这个 ON 后面的条件，ON 后面的条件，是指定 被驱动表 中不满足 ON 条件情况下依然要显示的关键。（在内连接中连接条件放 ON 和放 WHERE 效果一样）

如果外连接有几层，比如说三层：

1
2
3
4

SELECT *
FROM teacher t
  LEFT JOIN student ON t.id = stu.into
  LEFT JOIN scope scp ON stu.id = scope.stu_id;

那么上面这条查询需要怎么走呢，先查询老师所有的学生，得到一张中间表以后，再以这张中间表作为 驱动表 来查询 scope。

八.复杂条件查询

MySQL InnoDB 中存在着 SQL解析器，解析器可谓为了查询正确的数据而费尽心思，目的只有一个，就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器，为了执行效率比较快，会对字节码进行一些顺序的重新编排，什么 happen before 规则都出来了。

而什么东西查询最快呢，那就是查询常量的时候了。

8.1 整理查询语句

首先就是去除不必要的括号，因为括号如果没有意义存在，那移除了就更有利于优化器的解析了。

比如 WHERE (id = 1) 会被优化成 WHERE id = 1。这个好像也没什么好说的。

复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20 则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20。

8.2 简化查询条件

WHERE age > 18 AND real_age > age 则直接变成 WHERE age > 18 AND real_age > 18

8.3 删除废话条件

像我之前老师教的，在写 MyBatis Mapper.xml 的时候，因为 WHERE 总是需要动态的条件，所以前面会加一个 WHERE 1 = 1（为啥不用标签，因为标签可读性其实不怎么高）。

那么，如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'，那么语句将会被直接优化为 WHERE name LIKE 'Weidan%' 。这么想想好像直接写 WHERE 1 = 1 除了解析器多了点工作，好像也没什么所谓了。

8.4 计算表达式

WHERE age = 9 + 9 那么解析器会直接给你个 WHERE age = 18。不过如果这些计算方式放在了列名上，比如：

1
2

WHERE -age = -18
WHERE to_days(age) = 18

解析器害怕他也优化错了，所以也会放弃优化，一个简单的记忆就是函数发生在等号后面的常量值上，可以优化，但是如果需要依赖列的计算的话，那就放弃优化了。

8.5 必要时转换外连接到内连接

右外连接会被转换为左外连接，毕竟 左外连接 更好确定 驱动表 和 被驱动表。

那如果我们在查询 左外连接 的时候，暗示着我得出的结果中，被驱动表不含 NULL 的值，聪明的暖男解析器将会 GET 到这个信息，把 外连接 优化成 内连接。

比如上面的例子中：

1
2
3
4
5
6
7

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
  AND scp.id IS NOT NULL;

那么上面两个语句中是不是就都暗示解析器中，拿到的 scope 中的 id 不能为空。

所以！直接变成这条语句执行：

1
2
3
4
5
6

SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id;;

九.完

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。

那这里有个什么经验呢…就是我们可以根据经常使用常用的列来建立索引，先拿到 id，然后再去缓存命中，再走数据库~

单列聚簇索引还有个需要注意的点，就是这个列的辨识度要搞，如果这个列只有 MAN 和 WOMAN 的话，为这个列建立索引根本就没有什么用处，因为跟全表扫描一样的效率，优化器更偏向于全表扫描，所以切记不要给列值只有寥寥几个的列建立索引，纯属浪费。

5.2 多列非聚簇索引

如果是 name + mobile 联合索引的话，需要注意的点就有点多了：

每个数据页的排序就会变成，先按照 name 进行排序，然后再按照 mobile 进行排序。

5.4 什么时候不会使用索引

1.不满足最左匹配

我想大家都听过 最左匹配原则，就是这个意思，因为我的索引是先根据 name 排序再根据 mobile 进行排序的。那么查询的时候，如果加上 order by 的话，这个排序同样也是派上用场的。

但是如果说查询条件只是写了 WHERE mobile = '13800x1'，那上面的索引就完全派不上用场。

怎么说，因为我这个索引是结合了 name 先做排序然后索引的，你只是查询 mobile 的话，就需要遍历整个索引，拿到 id 后还需要回表，这个过程跟直接扫描 聚簇索引 相比，耗费的资源更多，所以，如果一个 name + mobile 的索引，只应用于带有 name 开始的查询条件。因为 name 在前面。这就是 最左匹配原则。

2.排序一个列使用升序一个使用降序

比如 WHERE name like 'xxx%' ORDER BY name DESC,mobile ASC，这样的情况只能用到 name 列的索引（也就是所有 mobile 失去了效果），然后再把所有列重新整理，依据 mobile 重新排序。

如果两个都是同一个方向的排序就不会出现这种情况。

3.VARCHAR 匹配前缀查询

WHERE name like '%狗蛋' 这种情况为什么不能使用索引呢，因为你前面未知啊，根据 name 排序的索引查询跟全表扫描有什么区别，还少了 回表 的操作，所以只能全表扫描，取出满足 xxx狗蛋 的数据了。

4.排序用到索引中没有的列

这个理解了 区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已 这句话，就知道为什么了，因为索引中的排序并不适合 SQL 指定的顺序。

5.使用函数修饰值的时候

比如 WHERE LOWER(name) = 'aa'，每个列都需要通过函数调用，那就跟全表扫描没什么区别了。

那如果 SQL 语句中，条件出现的顺序没有和多列索引的顺序一致的话，会怎么样：

完全不必担心这个问题，因为 SQL 在执行之前还会交给一个叫做 优化器 的东西进行整理，下面会说到，现在就只要知道他会把 SQL 条件整理成跟索引一样的顺序就好了。

既然多列索引可以帮忙查询条件中满足最左匹配的 SQL 语句，是不是越多越好，答案并不是，我觉得应该根据权重来区分，因为 非聚簇索引 他的索引列并不会像自增 ID 的索引树一样，顺序的插入数据（历史原因导致我们项目使用 UUID 做主键的哭晕在厕所），而是经常的造成 页拆分（也就是上面拆分的动图），所以 非聚簇索引 多了，增删改 需要维护这棵树平衡所做的 整容 就越多，严重的话会影响 增删改 的效率。

5.5 什么时候命中索引

那什么时候用到了索引，自然就是避免上面的情况就可以了，就有这些情况，包括但不局限于：

1. 条件覆盖了索引的最左列；
2. 常量查询，WHERE name = 'xxx' ；
3. 范围查询，满足 1 的情况下，比如 name > 'AA' 或者 name = 'AA' AND mobile > '13800';
4. 排序，但是需要用到的排序列是同一个方向进行排序的。
5. 分组，依然需要满足 1 条件，如果用到了 group by name，InnoDB 会先将相同的 name 放在一起，然后再继续根据其他条件进行运算。

5.6 回表代价

可以这么说，如果回表的代价过高，InnoDB解析器 可能直接决定，不要使用索引，直接全表扫描。

怎么回事，就是 非聚簇 索引他的值都是连在一起的，查询的时候，称为 顺序I/O，而 非聚簇索引 查询出来的 id 并不会连在一起，所以回表去查询 id 数据的时候，称为 随机I/O。而 随机I/O 的效率是很低的，所以当命中索引的数据行总是较多的时候，不如 全表扫描 来的快，所以可能出现 SQL 已经完全命中这个索引但是解析器他就是不使用。

怎么防止这种情况发生，就是让查询索引返回的数量少，比如我们可以 LIMIT 100 去限定只查询 100 条数据，或者我们只要查询索引中出现的列，比如 id 然后再在程序中，根据 id 列表去命中缓存，名不中的再一次性批量查库就可以了。

5.7 文件排序

有时候我们去解析 EXPLAIN 我们的 SQL 语句的时候，会出现 File Sort 类型，这个类型指的是，查询出来的结果不是按照我们 SQL 指定的顺序来的，所以需要在内存中（必要时借助硬盘）来重新对数据进行排序，这个过程就是 File Sort，那如何避免这个类型出现，那就是防止上面不命中索引的情况。

5.8 索引合并

使用等值且命中两个索引的列

比方说我的用户表有 name 索引 和 mobile 索引，那这个条件 WHERE name = 'Weidan' AND mobile = '18588777777' 就可以使用两个索引，然后取 id 的 交集，然后回表查询。但是如果 name > 'Weidan' 这种条件，就不会使用到合并。

但是但是，如果是主键列是范围的话，是可以的，因为他们合并的时候也会操作主键嘛。

不过有没有使用到，还要看成本，如果一个索引命中的数据太多，依然不会使用合并索引。

合并两个索引的列

依然需要满足 列都是等值查询 这个条件，比如 WHERE name = 'Weidan' OR mobile = '18588777777'，会合并两个主键再统一回表查询。

范围搜索合并查询

不过如果我们是范围查询，又想使用两个索引怎么办，我们可以把 name > 'Weidan' 以及 monile > '18588777777' 先查询出来 id 然后 union 在一起，再通过 id 去寻找我们想要的数据。

但是还是建议把需要合并的列作为一个 非聚簇 索引来覆盖，效率要高。

七.表连接查询

首先就以最经典的学生、成绩来做示例吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

CREATE TABLE `student` (
  `id` int(11) NOT NULL,
  `name` varchar(50) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `student` VALUES (1, '狗蛋');
INSERT INTO `student` VALUES (2, '狗剩');
INSERT INTO `student` VALUES (3, '翠花');
COMMIT;

DROP TABLE IF EXISTS `scope`;
CREATE TABLE `scope` (
  `id` int(11) NOT NULL,
  `subject` varchar(255) DEFAULT NULL,
  `scope` int(255) DEFAULT NULL,
  `stu_id` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

BEGIN;
INSERT INTO `scope` VALUES (1, '语文', 80, 1);
INSERT INTO `scope` VALUES (2, '数学', 98, 1);
INSERT INTO `scope` VALUES (3, '英语', 59, 2);
INSERT INTO `scope` VALUES (4, '政治', 79, 2);
COMMIT;

7.1 连表查询

那么先列举一个连表很普通的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SELECT * 
FROM student, scope;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  2 | 狗剩   |  1 | 语文    |    80 |      1 |
|  3 | 翠花   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  2 | 数学    |    98 |      1 |
|  3 | 翠花   |  2 | 数学    |    98 |      1 |
|  1 | 狗蛋   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  3 | 翠花   |  3 | 英语    |    59 |      2 |
|  1 | 狗蛋   |  4 | 政治    |    79 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
|  3 | 翠花   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
12 rows in set (0.00 sec)

可以看到，如果我们不加任何条件，直接就连接两张表的话，取出来的结果就是第一张表所有的数据，去搭配第二张表所有的数据，也就是第一张表有 3 条数据，第二张表有 4 条记录，结果就有 3 ✖ 4 = 12 条记录。这个过程也称为 笛卡尔积。这种情况在日常编程中应该也没人会这么写的吧，仔细想想，如果两张表都是百万级别的数据，笛卡尔积是多恐怖的一件事情。

7.2 内连接

就是由于上面的结果集一般我们都不需要，所以我们会加上一些条件加以限制：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id;

+----+--------+----+---------+-------+--------+
| id | name   | id | subject | scope | stu_id |
+----+--------+----+---------+-------+--------+
|  1 | 狗蛋   |  1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |  2 | 数学    |    98 |      1 |
|  2 | 狗剩   |  3 | 英语    |    59 |      2 |
|  2 | 狗剩   |  4 | 政治    |    79 |      2 |
+----+--------+----+---------+-------+--------+
4 rows in set (0.00 sec)

这就是我们想要的结果集，所有参考学生的考试成绩。

而 InnoDB 是怎样的实现两个表连接的呢，这时候，优化器会根据查询成本确定 驱动表 和 被驱动表。

• 驱动表：先查询的那个表，这里假设是 student 表，所以执行的时候，第一步执行 SELECT * FROM student;；

• 被驱动表：查询出来驱动表所有的数据以后，就会根据驱动表中每一条数据，去执行被驱动表。

  • 比如我现在 student 有三条记录，分别 id 是 1 2 3；
  • 然后对三条记录分别执行 SELECT * FROM scope WHERE stu_id = ?；
  • 因为 scope 表中不存在 翠花 的成绩，所以 SELECT * FROM scope WHERE stu_id = 3 并没有展示出来，因为这个语句相当于 SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = 3

那如果上面的语句加上其他条件会怎么样，比如：

1
2
3
4
5

# 查询成绩 90 分以上的学生成绩信息
SELECT stu.*, scp.*
FROM student stu, scope scp
WHERE stu.id = scp.stu_id
  AND scp.scope > 90;

那在访问驱动表 student 的时候同上面一样，但是针对驱动表中每一条数据执行被驱动表的时候，就会变成：

SELECT * FROM scope WHERE stu_id NOT NULL AND stu_id = ? AND scope > 90;

一句话就是说，这些条件针对哪个表，在执行那个表的时候就会带上指定的条件。

内连接推荐写法：

1
2
3

SELECT stu.*, scp.*
FROM student stu INNER JOIN scope scp ON stu.id = scp.stu_id
WHERE scp.scope > 90;

效率没有变高，但是可读性变好，在我看来，特定的限定功能就需要放在特定的位置，连接条件在 ON 后面，而查询条件在 WHERE 后面，也可以很好的跟下面的外连接写法统一。

7.3 外连接

外连接的目的是将连接在一起查询的表中，以某个表为主要目的，查询他在另外一个表的所有信息，包括不存在的信息。比如还是上面的例子，翠花她是个坏学生，一个科目都没有参加考试，但是老师如果通过上面的内连接查询来看的话，可能都不知道还有这个人的存在。这就麻烦大了啊，家长上门投诉，我给你钱了，她没参加考试你都不管管的吗。所以这时候，就需要外连接来做这个事情了：

1
2
3
4
5
6
7
8
9
10
11
12

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
+----+--------+------+---------+-------+--------+
| id | name   | id   | subject | scope | stu_id |
+----+--------+------+---------+-------+--------+
|  1 | 狗蛋   |    1 | 语文    |    80 |      1 |
|  1 | 狗蛋   |    2 | 数学    |    98 |      1 |
|  2 | 狗剩   |    3 | 英语    |    59 |      2 |
|  2 | 狗剩   |    4 | 政治    |    79 |      2 |
|  3 | 翠花   | NULL | NULL    |  NULL |   NULL |
+----+--------+------+---------+-------+--------+
5 rows in set (0.00 sec)			

这个时候，嗯哼，一抓一个准，没有来考试的，在 scope 表的字段中，显示为 NULL。

关于 驱动表 和 被驱动表 的含义已经在上面内连接的内容中指定，那么如果说 内连接 是根据成本来指定 驱动表 的，那 外连接 就是我们来指定驱动表。

以 驱动表 所有满足我们条件的数据，来查询 被驱动表，如果 被驱动表 不存在 驱动表 中某条数据的关联，显示为 NULL。

那么关键点在哪里，就在这个 ON 后面的条件，ON 后面的条件，是指定 被驱动表 中不满足 ON 条件情况下依然要显示的关键。（在内连接中连接条件放 ON 和放 WHERE 效果一样）

如果外连接有几层，比如说三层：

1
2
3
4

SELECT *
FROM teacher t
  LEFT JOIN student ON t.id = stu.into
  LEFT JOIN scope scp ON stu.id = scope.stu_id;

那么上面这条查询需要怎么走呢，先查询老师所有的学生，得到一张中间表以后，再以这张中间表作为 驱动表 来查询 scope。

八.复杂条件查询

MySQL InnoDB 中存在着 SQL解析器，解析器可谓为了查询正确的数据而费尽心思，目的只有一个，就是较快的查询出来正确的数据。其实这里也可以联想到 jvm编译器，为了执行效率比较快，会对字节码进行一些顺序的重新编排，什么 happen before 规则都出来了。

而什么东西查询最快呢，那就是查询常量的时候了。

8.1 整理查询语句

首先就是去除不必要的括号，因为括号如果没有意义存在，那移除了就更有利于优化器的解析了。

比如 WHERE (id = 1) 会被优化成 WHERE id = 1。这个好像也没什么好说的。

复杂一点的 WHERE (id = 1 AND name = 'WEIDAN') AND age = 20 则会被优化成 WHERE id = 1 AND name = 'WEIDAN' AND age = 20。

8.2 简化查询条件

WHERE age > 18 AND real_age > age 则直接变成 WHERE age > 18 AND real_age > 18

8.3 删除废话条件

像我之前老师教的，在写 MyBatis Mapper.xml 的时候，因为 WHERE 总是需要动态的条件，所以前面会加一个 WHERE 1 = 1（为啥不用标签，因为标签可读性其实不怎么高）。

那么，如果我写的是 WHERE 1 = 1 AND name LIKE 'Weidan%'，那么语句将会被直接优化为 WHERE name LIKE 'Weidan%' 。这么想想好像直接写 WHERE 1 = 1 除了解析器多了点工作，好像也没什么所谓了。

8.4 计算表达式

WHERE age = 9 + 9 那么解析器会直接给你个 WHERE age = 18。不过如果这些计算方式放在了列名上，比如：

1
2

WHERE -age = -18
WHERE to_days(age) = 18

解析器害怕他也优化错了，所以也会放弃优化，一个简单的记忆就是函数发生在等号后面的常量值上，可以优化，但是如果需要依赖列的计算的话，那就放弃优化了。

8.5 必要时转换外连接到内连接

右外连接会被转换为左外连接，毕竟 左外连接 更好确定 驱动表 和 被驱动表。

那如果我们在查询 左外连接 的时候，暗示着我得出的结果中，被驱动表不含 NULL 的值，聪明的暖男解析器将会 GET 到这个信息，把 外连接 优化成 内连接。

比如上面的例子中：

1
2
3
4
5
6
7

SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu LEFT JOIN scope scp ON scp.stu_id = stu.id;
  AND scp.id IS NOT NULL;

那么上面两个语句中是不是就都暗示解析器中，拿到的 scope 中的 id 不能为空。

所以！直接变成这条语句执行：

1
2
3
4
5
6

SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id
  AND scp.id = 1;
  
SELECT * 
FROM student stu INNER JOIN scope scp ON scp.stu_id = stu.id;;

九.完

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

一.InnoDB表数据

上面聊了这么多这个结构，那个结构的。现在是不是有点好奇，InnoDB 是把数据存在哪里的。答案也很简单，存在一颗 B+ 树种。

在 InnoDB 中，数据所在的位置没有其他地方，就只有一颗 B+ 树。而我们自己建立的索引，也是一颗 B+ 树。存储完整数据的 B+ 树也叫 聚簇索引，而我们自定义的列索引的 B+ 树，则称为 非聚簇索引。

OK，大概明白了这两个东西以后，我们一个一个拆开来说说。

二.B+树是什么

关乎数据结构的东西了，如果觉得很简单，或者说已经学过脑袋有印象，可以跳过这段一个非计算机老男人写的废话。

说 B+ 树，一切要从一个最简单的例子开始，就是二分查找法。

2.1 二分查找法

我们在聚合的时候，估计都玩过一个游戏，叫做大冒险。确定谁来大冒险，有个方式就是猜数字：由上一轮中的倒霉鬼，来确定一个数字，然后围成一圈的小伙伴们来猜。猜中了，就是下一个倒霉鬼。

那怎么猜的呢，这个倒霉鬼在手机上输入一个数字，盖在地上防止修改。然后从一圈中某个人开始，说一个数字，那么那个站在台上的倒霉蛋就会缩小范围，让下一个人继续猜：

比如数字是69。

那么就有下面的对话：

1
2
3
4
5
6

A: 50
倒霉：50 - 100
B：75
倒霉：50 - 75
C：69
倒霉：恭喜你答对了balabala

这个过程咧，有没有很熟悉，对，就是 二分查找法。

那为啥使用二分查找法呢，肯定是因为性能好啊。

那比如我有个 有序 数组：[18, 53, 55, 147, 151, 495, 551, 606, 638, 728]。

我一次查询每一个数字，平均次数是 (1+2+3+4+5+6+7+8+9+10)/10 = 5.5次，而使用二分查找法则是 4+3+2+4+3+1+4+3+2+3)/10 = 2.9次。顺序查找最坏的情况也要 10 次，而二分查找最坏是 4 次。这么好的查找效率没有理由不用他。

2.2 二叉查找树

那二分查找和树什么关系，这里就要说到 二叉查找树，根据百度百科的定义：

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

那么我现在把上面的数组转换成 二叉查找树，并且给予一个查找的动图：

查询看起来是很方便，但是对数据的增删查改就不是这样的了。有时候，数据插入多了，如果不调整可能会所有都放在了左边或者右边，这样性能就会越来越接近顺序查找。那么，数学家就提出了 平衡二叉树 和 最优二叉树 的定义。

2.3 平衡二叉树

平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1。这样子就可以让树变得矮胖矮胖的好身材，至于为啥矮胖矮胖才是好身材，因为这样子的话，查询效率才高啊。

比如下面这颗，查找大于 495 的时候，简直就是线性查找的效率了。

那长得丑怎么办，整容（旋转跳跃我闭着眼）啊，不过需要钱（性能）。

那我现在就按照 二叉查找树 那一颗，来插入一个 999，平衡二叉树是在增删改的时候通过旋转来平衡树。

那么有长得帅的读者就要问了，这个跟 B+树 是什么关系。

2.4 B+树

因为 B+树 跟上面的思想差不多，所以，现在就来说说 B+树。

B+树 她不是二叉树，但是查询跟 二叉树 差不多，我先放一颗 B+树。

这是一颗高度为 2 扇出为 5 的 B+树。

那这个怎么实现查找的呢，现在比方说我要查找 606 这条数据：

那么 B+树 是怎么实现新增，然后平衡的呢，跟上面一样发生旋转。旋转的规则如下：

叶子节点是第二层的数据，索引节点是第一层查找时用到的数据。那旋转的情况就是节点页有没有满了：

第一种就不用演示了，比如新增 1000 直接存入最后边的叶子节点就好了。

接下来我演示第二种，那我就插入 645 这个数字吧。

可以从图中看到，拆分页是多么耗性能的一个东西了，所以我们经常说顺序插入是最好的性能，也要求主键一般呈递增的状态。

但是当左右兄弟节点可能没有满的时候，InnoDB不会急着去拆分数据页，而是会通过旋转的方式来让树达到平衡。这里就不说了。

那如果是第三种情况呢，拆分索引页跟拆分数据页是同样的道理，我就不画出来了，只要知道如果是第三种，性能还要比第二种低一倍，因为不仅拆分数据页，还拆分索引页了。

那如果页中有记录被删除呢，怎么去平衡，这时候就有一个东西叫做 计算因子，如果删除后的页的记录数量小于 计算因子*总页数 的时候，B+ 树会去做 合并操作。那我就继续用这一组数据来做示例。

删除 606 638 以后，B+ 树就会变成下面这个样子：

所以说，B+ 树在发生了修改以后，为了保证查询效率，会对某个一部分的节点进行整容。

三.InnoDB是怎么用B+树

好，结合上一篇的 InnoDB表结构 中的页和数据行的结构，以及刚刚所说的 B+树，现在我们就可以来看看一个表中的数据，是怎样被存储以及怎样被查询的。

从之前我们知道，数据是按照数据页的方式进行存放的，而数据页里面除了记录我们的用户记录行意外，还有一些额外的属性用来表示这一页的类型（所以数据页不仅仅是存放数据的页，也可能是 undo页 等等），而数据行里面也有一些额外的属性来辅助查找。

3.1 查找数据所在的页

之前已经系统的列举过 数据页 和 数据行 的所有属性，现在我就挑在索引中需要用到的属性放在图中就可以了，放上其他的没什么用处，也占用地方。

那我现在就假设，上一节中的叶子节点中的数据（如下图），就是我们一条记录的主键 id，因为我们的记录肯定不止有主键这么简单，所以应该还有其他数据，我暂时使用一些占位的方框做代替。

那么这时候上面在数据在 MySQL 数据页中的结构，应该是这样子的：

叶子节点之间的关系，记录类型中：2 表示最小记录，3 表示最大记录，0 表示用户记录。那如果这棵树没有非叶子节点的话，搜索就是线性的需要一个一个遍历，这时候怎么办咧，B+树 的结构就出现了。

这个结构，就是上面 B+树 在 InnoDB 中数据页的结构了。

3.2 查找真实数据

那么，上面我演示的一个页有三个记录，但其实不止三个记录，我就假设一个页有 16 条记录（其实不止，根据数据的大小）吧。那通过索引只能找到这一页呀，难道要一个一个遍历查询相对应的数据，这时候使用遍历还是有点早了（毕竟遍历并没有那么高效），所以在每个数据页中，又使用了一个槽进行分区。

那现在把镜头切换到一个页中来：

InnoDB 会把一个页中的所有数据根据一个很小的基数，比如 4 个记录为一组，去划分分组。那么每个组在数据页中都有对应的槽来记录分组的最大值。

那按照上面的数据，比如我要查询 55。

槽0 = 18，槽1 = 54，槽2 = 64，槽3 = 77。

怎么找呢，类似于上面那个二分查找的游戏，槽0 说 18，老大说 18-77 之间，槽1 说 54，老大说 54-77，直到最后，确定数字是在 槽1 和 槽2 之间，因为 槽2 = 64 大于 55，而 槽1 = 54 小于 55。所以从 槽1 的最大值 54 开始寻找下一条记录，遍历分组里面的数据行（因为这时候需要遍历的长度已经被切到很小了，所以是时候用遍历来做了，因为用其他算法的次数跟遍历差不多），取出 55 这条数据。

那整个查询过程中，需要跟硬盘交互的并不多，我们知道，InnoDB 是通过数据页来进行硬盘与内存的沟通的，查找效率高就意味着，我需要从硬盘取数据的次数越少。

3.3 删除记录

删除记录时，InnoDB 是怎么做的，就是在之前提到的数据行的头信息的 delete_flag 设置为 1，这条记录就会被放入 垃圾链表，当又需要插入新数据的时候，会判断是否合适放在这个位置，再把原来的数据给覆盖掉。

为什么这么做无非就是减少 硬盘IO。如果真的删除的话，需要去同步硬盘，这个过程并不是很重要，所以先标记就好了。

然后这条记录的上一条记录的 next_record 字段将被重新指向当前删除记录的下一条记录。

四.聚簇索引

那聚簇索引是什么，其实看了上面的图，加点料就可以了：

其实上面的例子我使用的是 id 来做例子，但是每条记录还带有其他所有列的信息（非 NULL）的，如果有 NULL 则会被记录在记录头信息，然后节省了存储数据的空间。

而这种索引，叫做 聚簇索引，意思是什么咧，就是一条记录保存了完整的数据信息，非聚簇则不是。而每条数据都会有一个 primary key，如果没有，InnoDB 会自动加上这个隐藏的列。这也是 MySQL_InnoDB 结构的库保存数据的方式。

所以可以这么说，InnoDB 就是 B+树 构成的。而根节点从建立表开始将会被记录，之后每次查询都会从这个根节点开始查询。

五.非聚簇索引

5.1 简单非聚簇索引

那 非聚簇索引 和 聚簇索引 有什么区别，区别在于 非聚簇索引 并没有存放整条记录的所有数据，只是存放了 索引列 和 主键 而已。所以当我们通过 非聚簇索引 查询一条数据行的所有列的时候，就需要 回表 去查询其他列的信息了，也就是说需要 两次查询 才完成这个需求。

比方一个表：

1
2
3
4
5
6

CREATE TABLE trbac_user (
  id BIGINT auto_increase,
  name varchar(50) NOT NULL,
  mobile varchar(50) NOT NULL
  PRIMARY KEY(id)
)

那我使用 name 来做非聚簇索引，这时候 InnoDB 就有一颗以 name 来查询的 B+树：

那我们可以看到，数据行并没有覆盖所有数据，只有 name + id。那比如我们只是查询 name 或者 id 列，就可以直接在这里返回去了。

但是如果我还想要知道 mobile 列的话，这时候就需要在上面那棵树拿到 id，然后再去 id 那棵树查询其他的列信息。

需要从下面的主键的数据页来查询其他数据。